package sorting;

import java.util.Arrays;

public class SelectSort {

    /**
     * 旧金山大学笔记：
     * 重复（元素个数-1）次
     * 把第一个没有排序过的元素设置为最小值
     * 遍历每个没有排序过的元素
     * 如果元素 < 现在的最小值
     * 将此元素设置成为新的最小值
     * 将最小值和第一个没有排序过的位置交换
     */

    public static int[] selectSort(int[] targetArr) {
        //copy
        int[] arr = Arrays.copyOf(targetArr, targetArr.length);

        if (arr == null || arr.length < 2) {
            return arr;
        }
        for (int i = 0; i < arr.length; i++) {
            //**核心代码**记录最小值得数组下标。 类似插入排序需要插入得数 原理类似
            int minIndex = i;
            //这里排序好的即最小值 或者遍历那些未排序的 即从i开始
            for (int j = i; j < arr.length; j++) {
                if (arr[j] < arr[minIndex]) {//找到未排序中得最小的数
                    minIndex = j; //将最小数的索引保存
                }
            }
            //交换。
            swap(arr, i, minIndex);
        }
        return arr;
    }

    public static void swap(int[] array, int i, int j) {
        int temp = array[j];
        array[j] = array[i];
        array[i] = temp;
    }

    public static void main(String[] args) {
        int[] targetArr = {10, 1, 17, 16, 60, 64, 33, 21, 7};
        System.out.println(Arrays.toString(selectSort(targetArr)));
    }
}
